package org.example;

public class Test1 {
    //leetcode 654 最大二叉树 https://leetcode.cn/problems/maximum-binary-tree/description/
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryChildTree(nums,0,nums.length - 1);
    }

    public TreeNode constructMaximumBinaryChildTree(int[] nums, int left, int right) {
        if (left > right) return null;
        int pivot = findMax(nums,left,right);
        TreeNode root = new TreeNode(nums[pivot]);
        root.left = constructMaximumBinaryChildTree(nums,left,pivot - 1);
        root.right = constructMaximumBinaryChildTree(nums,pivot + 1, right);
        return root;
    }

    public int findMax(int[] nums, int left, int right) {
        int ret = -1,max = -1;
        for (int i = left; i <= right; i++) {
            if (nums[i] > max) {
                max = nums[i];
                ret = i;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        int[] arr = {3,2,1,6,0,5};
        test1.constructMaximumBinaryTree(arr);
        System.out.println(999);
    }
}
